/********************************************************************************
* @Author: Zhenzhou Liu
* @Date: 2024-08-28
* @Description: 矩阵图解题代码
********************************************************************************/
#ifndef GRAPHTHEORY_MATRIXGRAPH_H
#define GRAPHTHEORY_MATRIXGRAPH_H
#include <stdio.h>

int findParent(int *parent, int index) {
    if (parent[index] != index) {
        parent[index] = findParent(parent, parent[index]);
    }
    return parent[index];
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void unionFind(int *parent, int *rank, int x, int y, int *count) {
    int rootX = findParent(parent, x), rootY = findParent(parent, y);

    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            swap(&rootX, &rootY);
        }
        parent[rootY] = rootX;
        if (rank[rootX] == rank[rootY]) {
            rank[rootX] += 1;
        }
        --(*count);
    }
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int m = gridSize,  n = gridColSize[0];
    int parent[m * n], rank[m * n], count = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int index = i * n + j;
            if (grid[i][j] == '1') {
                parent[index] = index;
                ++count;
            } else {
                parent[index] = -1;
            }
            rank[index] = 0;
        }
    }

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int index = i * n + j;
            if (grid[i][j] == '1') {
                grid[i][j] = '0';
                if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                    unionFind(parent, rank, index, index - n, &count);
                }
                if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                    unionFind(parent, rank, index, index - 1, &count);
                }
                if (i + 1 < m && grid[i + 1][j] == '1') {
                    unionFind(parent, rank, index, index + n, &count);
                }
                if (j + 1 < n && grid[i][j + 1] == '1') {
                    unionFind(parent, rank, index, index + 1, &count);
                }
            }
        }
    }

    return count;
}

int m, n;
int directions[][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};


void dfsForEnclaves(int** grid, int x, int y)
{
    for (int i = 0; i < 4; ++i)
    {
        int nx = x + directions[i][0], ny = y + directions[i][1];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1)
        {
            grid[nx][ny] = 0;
            dfsForEnclaves(grid, nx, ny);
        }
    }
}

int numEnclaves(int** grid, int gridSize, int* gridColSize){
    m = gridSize, n = gridColSize[0];
    for (int i = 0; i < m; ++i)
    {
        if (grid[i][0] == 1)
        {
            grid[i][0] = 0;
            dfsForEnclaves(grid, i, 0);
        }
        if (grid[i][n - 1] == 1)
        {
            grid[i][n - 1] = 0;
            dfsForEnclaves(grid, i, n - 1);
        }
    }

    for (int j = 1; j < n - 1; ++j)
    {
        if (grid[0][j] == 1)
        {
            grid[0][j] = 0;
            dfsForEnclaves(grid, 0, j);
        }
        if (grid[m - 1][j] == 1)
        {
            grid[m - 1][j] = 0;
            dfsForEnclaves(grid, m - 1, j);
        }
    }

    int enclavesCount = 0;
    for (int i = 1; i < m - 1; ++i)
    {
        for (int j = 1; j < n - 1; ++j)
        {
            if (grid[i][j] == 1)
                ++enclavesCount;
        }
    }
    return enclavesCount;
}

bool dfsForClosedIsland(int** grid, int m, int n, int i, int j)
{
    if (i < 0)
}


int closedIsland(int** grid, int gridSize, int* gridColSize) {

}

#endif //GRAPHTHEORY_MATRIXGRAPH_H
